import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-22
 * Time: 8:51
 */

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    private void backTracking(int index,int k,int n){
        if(k==list.size()){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = index;i<=n;++i){
            list.add(i);
            backTracking(i+1,k,n);
            list.removeLast();
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        backTracking(1,k,n);
        return ret;
    }
}

public class TestDemo {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.combine(4,2);
    }
}
